#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/*
 * 面试题 08.12. 八皇后
提示
困难
178
相关企业
设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

注意：本题相对原题做了扩展
 *
 * */


vector<vector<string> > ret;
vector<string> temp;

//这个写的有毛病只考虑了一个/ 这种斜边
//是否可以放下
//bool check(int row,int col,int n)
//{
//    //行检测
//    for (int i = 0; i <n ; ++i) {
//        if( temp[i][col]=='Q')
//        {
//            return false;
//        }
//    }
//    //lie
//    for (int i = 0; i <n ; ++i) {
//        if( temp[row][i]=='Q')
//        {
//            return false;
//        }
//    }
//
//    //斜边检测
//    int trow=row;
//    int tcol=col;
//    //斜上方走
//    while (trow>=0&&tcol<n)
//    {
//        if (temp[trow][tcol]=='Q')
//        {
//            return false;
//        }
//
//        trow--;
//        tcol++;
//    }
//    //斜下方走
//    while(row<n&&col>=0)
//    {
//        if (temp[row][col]=='Q')
//        {
//            return false;
//        }
//        row++;
//        col--;
//    }
//
//    return true;
//}

bool isUsed(int row, int col, int n) {

    int trow = row;
    int tcol = col;

    //检测本位置 以及斜边 以及竖着的 以及横着的 是否被占用
    //heng方向
    for (int i = 0; i < n; ++i) {
        if (temp[row][i] == 'Q')
            return true;
    }
    //lie
    for (int i = 0; i < n; ++i) {
        if (temp[i][col] == 'Q')
            return true;
    }

    //斜边
    //先减到

    //从当前位置 斜上
    while (trow >= 0 && tcol >= 0) {
        if (temp[trow--][tcol--] == 'Q')
            return true;
    }

    tcol = col;
    trow = row;
    //向右下
    while (trow < n && tcol < n) {
        if (temp[trow++][tcol++] == 'Q')
            return true;
    }
    tcol = col;
    trow = row;
    //右上 row--； col++
    while (trow >= 0 && tcol < n) {
        if (temp[trow--][tcol++] == 'Q')
            return true;
    }
    tcol = col;
    trow = row;
    //左下 col-- row++
    while (trow < n && tcol >= 0) {
        if (temp[trow++][tcol--] == 'Q')
            return true;
    }


    return false;
}

void dfs(int n, int sizer, int row) {
    if (sizer > n)
        return;

    if (sizer == n) {
        ret.push_back(temp);
        return;
    }

    //这里单个for循环就行了因为一行就只能放一个
    for (int j = 0; j < n; ++j) {
        if (check(row, j, n))
            continue;

        temp[row][j] = 'Q';
        dfs(n, sizer + 1, row + 1);
        temp[row][j] = '.';
    }


}

vector<vector<string>> solveNQueens(int n) {

    //初始化为.
    temp.resize(n, string(n, '.'));

    dfs(n, 0, 0);

    return ret;
}
